/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***普通二叉树（非有序二叉树）的创建、递归和查找、删除节点    P94 ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

class HeroNode
{
public:
    HeroNode() = delete;
    //构造函数
    HeroNode(int id, string name, HeroNode *left, HeroNode *right) : id(id), name(name), left(left), right(right) {}
    HeroNode(int id, string name) : id(id), name(name), left(nullptr), right(nullptr) {}
    //删除拷贝构造
    HeroNode(HeroNode &) = delete;
    string transToString()
    {
        // cout << "id=" << id << ",name=" << name << endl;
        return string("id=" + std::to_string(id) + "\t" + "name=" + name);
    }
    int getId()
    {
        return this->id;
    }
    void setId(int id)
    {
        this->id = id;
    }
    string getName()
    {
        return this->name;
    }
    void setName(string name)
    {
        this->name = name;
        return;
    }
    HeroNode *getLeft()
    {
        return this->left;
    }
    void setLeft(HeroNode *left)
    {
        this->left = left;
        return;
    }
    HeroNode *getRight()
    {
        return this->right;
    }
    void setRight(HeroNode *right)
    {
        this->right = right;
        return;
    }
    //前序遍历
    void preOrder()
    {
        cout << this->transToString() << endl;
        if (this->left != nullptr)
        {
            this->left->preOrder();
        }
        if (this->right != nullptr)
        {
            this->right->preOrder();
        }
        return;
    }
    //中序遍历
    void midOrder()
    {
        if (this->left != nullptr)
        {
            this->left->midOrder();
        }
        cout << this->transToString() << endl;
        if (this->right != nullptr)
        {
            this->right->midOrder();
        }
    }
    //后序遍历
    void postOrder()
    {
        if (this->left != nullptr)
        {
            this->left->postOrder();
        }
        if (this->right != nullptr)
        {
            this->right->postOrder();
        }
        cout << this->transToString() << endl;
        return;
    }
    //前序查找，中序查找和后序查找
    HeroNode *preFind(int id)
    {
        if (this->id == id)
        {
            cout << "节点已经找到，信息为如下：" << endl;
            // cout<<this->transToString()<<endl;
            return this;
        }
        HeroNode *resNode = nullptr;
        if (this->left != nullptr)
        {
            resNode = this->left->preFind(id);
            if (resNode != nullptr)
            {
                return resNode;
            }
        }

        if (this->right != nullptr)
        {
            resNode = this->right->preFind(id);
        }
        return resNode;
    }
    HeroNode *midFind(int id)
    {
        HeroNode *resNode = nullptr;
        if (this->left != nullptr)
        {
            resNode = this->left->preFind(id);
            if (resNode != nullptr)
            {
                return resNode;
            }
        }
        if (this->id == id)
        {
            return this;
        }
        if (this->right != nullptr)
        {
            resNode = this->right->preFind(id);
        }
        return resNode;
    }
    HeroNode *postFind(int id)
    {
        HeroNode *resNode = nullptr;
        if (this->left != nullptr)
        {
            resNode = this->left->preFind(id);
        }
        if (this->right != nullptr)
        {
            resNode = this->right->preFind(id);
            if (resNode != nullptr)
            {
                return resNode;
            }
        }
        if (this->id == id)
        {
            return this;
        }
        return resNode;
    }
    //节点删除函数
    void delNode(int id)
    {
        //判断当前节点下一个节点是否是要被删除的节点
        //判断当前节点的左子节点是否是被删除的节点
        if ((this->getLeft() != nullptr) && (this->getLeft()->getId() == id))
        {
            delete this->getLeft();
            this->left=nullptr;
            return;
        }
        //判断当前节点的右子节点是否是被删除的节点
        if ((this->getRight() != nullptr) && (this->getRight()->getId() == id))
        {
            delete this->getRight();
            this->right=nullptr;
            return;
        }
        //递归向下查找
        if (this->left!=nullptr){
            this->left->delNode(id);
        }
        if (this->right!=nullptr){
            this->right->delNode(id);
        }
    }
    //这个析构有点难度~~~ 使用后序遍历来释放二叉树
    ~HeroNode()
    {
        if (this->left==nullptr && this->right==nullptr){
            return;
        }
        if (this->left != nullptr)
        {
            delete this->left;
            this->left = nullptr;
        }
        if (this->right != nullptr)
        {
            delete right;
            right = nullptr;
        }
      
    }

private:
    int id;
    string name;
    HeroNode *left;
    HeroNode *right;
};
//创建一棵二叉树
class BinaryTree
{
public:
    BinaryTree() : root(nullptr) {}
    BinaryTree(HeroNode *root) : root(root) {}
    BinaryTree(BinaryTree &) = delete;
    HeroNode *getRoot()
    {
        return this->root;
    }
    void setRoot(HeroNode *root)
    {
        this->root = root;
    }
    //二叉树的前中后序遍历
    void preOrder()
    {
        if (root != nullptr)
        {
            this->root->preOrder();
        }
        else
        {
            cout << "当前二叉树为空，无法遍历！" << endl;
        }
    }
    void midOrder()
    {
        if (root != nullptr)

        {
            this->root->midOrder();
        }
        else
        {
            cout << "当前二叉树为空，无法遍历！" << endl;
        }
    }
    void postOrder()
    {
        if (root != nullptr)

        {
            this->root->postOrder();
        }
        else
        {
            cout << "当前二叉树为空，无法遍历！" << endl;
        }
    }
    HeroNode *preFind(int id)
    {
        return root->preFind(id);
    }
    HeroNode *midFind(int id)
    {
        return root->midFind(id);
    }
    HeroNode *postFind(int id)
    {
        return root->postFind(id);
    }
    void delNode(int id)
    {
        if (root == nullptr)
        {
            cout << "当前二叉树为空，无法删除" << endl;
            return;
        }
        else if (root->getId() == id)
        {
            delete root;
        }
        else
        {
            root->delNode(id);
        }
        return;
    }
    //二叉树的析构！我的神呐~~~
    ~BinaryTree()
    {
        if (root != nullptr)
        {
            delete root;
            root = nullptr;
        }
    }

private:
    HeroNode *root;
};

int main()
{
    //先手动创建，并插入节点
    HeroNode *root = new HeroNode(1, "宋江");
    HeroNode *node2 = new HeroNode(2, "吴用");
    HeroNode *node3 = new HeroNode(3, "卢俊义");
    HeroNode *node4 = new HeroNode(4, "林冲");
    HeroNode *node5 = new HeroNode(5, "关胜");
    BinaryTree *newTree = new BinaryTree(root);
    root->setLeft(node2);
    root->setRight(node3);
    root->getRight()->setRight(node4);
    root->getRight()->setLeft(node5);
    cout << "前序遍历:" << endl;
    newTree->preOrder();
    cout << "中序遍历:" << endl;
    newTree->midOrder();
    cout << "后序遍历:" << endl;
    newTree->postOrder();
    //前序、中序和后序查找
    HeroNode *node = newTree->preFind(100);
    if (node != nullptr)
    {
        cout << "查询到信息如下" << endl;
        cout << node->transToString() << endl;
    }
    else
    {
        cout << "没有查询到该信息" << endl;
    }
    newTree->delNode(1);
    newTree->preOrder();
    delete newTree;
    return 0;
}